package com.longge;

import java.util.Arrays;
import java.util.Comparator;

public class MaxTaxiEarnings {

    public long maxTaxiEarnings(int n, int[][] rides) {

        Arrays.sort(rides, Comparator.comparingInt(a -> a[1]));
        int m = rides.length;
        long[] dp = new long[m + 1];
        for (int i = 0; i < m; i++) {
            int j = binarySearch(rides,i,rides[i][0]);
            dp[i+1] = Math.max(dp[i],rides[j][1]-rides[j][0]+rides[j][2]);
        }
        return dp[m];

    }

    private int binarySearch(int[][] rides, int hight, int target) {
        int low = 0;
        while (low<hight){
            int mid = low+(hight-low)/2;
            if (rides[mid][1]>target){
                hight=mid;
            }else {
                low = mid+1;
            }
        }
        return low;

    }
}
